/********** 线性递归与迭代 **********/
// 递归过程
// n! = n * (n-1)!
// 线性递归
function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

// 线性迭代
function factorial2(n) {
  return factIter(n, 1, 1);

  function factIter(n, counter = 1, product = 1) {
    if (counter > n) return product; // 结束 跳出的判断
    return factIter(n, counter + 1, product * counter);
  }
}

/********** 树形递归 **********/

// 1, 2, 5, 10
function countChange(amount) {
  return ccIter(amount);

  // 目前使用的货币类型
  function ccIter(amount, n = 0) {
    const TYPES = [1, 2, 5, 10];

    if (amount === 0) return 1;
    if (amount < 0 || n >= TYPES.length) return 0;

    return ccIter(amount, n + 1) + ccIter(amount - TYPES[n], n);
  }
}

// console.log(countChange(10));

/********** 练习：求幂 **********/
function fib(n) {
  return iter(n);

  function iter(k, current = 0, next = 1) {
    if (k === 0) return current;
    return iter(k - 1, next, current + next);
  }
}

// b ** n = b * b ** (n-1)
function expt(b, n) {
  if (n === 0) return 1;
  return b * expt(b, n - 1);
}
// 转换成迭代模式
// step === 1
// 2**4 === 2 * 2**3 === 2 * 2 * 2**2 === 2 * 2 * 2 * 2**1
// 2**4 === 2**2 * 2**2
// 2**8 === 2**4 * 2**4 === 2**2 * 2**2
// 如何提高时间效率？
function fastExpt(b, n) {
  return exptIter(b, n, 1);

  function exptIter(b, n, a) {
    if (n === 0) return a;
    if (n % 2) return exptIter(b ** 2, n / 2, a);
    return exptIter(b, n - 1, b * a);
  }
}

module.exports = {
  fib,
};
